{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8de6b225",
   "metadata": {},
   "source": [
    "## Content\n",
    "* Concepts of Functional Programming\n",
    "* Recursive Function\n",
    "* Mapping\n",
    "* Filtering\n",
    "* Reducing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8ac06db",
   "metadata": {},
   "source": [
    "## Concepts of Functional Programming\n",
    "\n",
    "* Functional programming is a programming paradigm in which we try to bind everything in __pure mathematical functions style__. \n",
    "* It is a declarative type of programming style. \n",
    "* Its main focus is on __“what to solve”__ in contrast to an imperative style where the main focus is __“how to solve“__. \n",
    "* It uses __expressions__ instead of statements. An expression is evaluated to produce a value whereas a statement is executed to assign variables."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "543c44a5",
   "metadata": {},
   "source": [
    "Any Functional programming language is expected to follow these concepts:\n",
    "* __Pure Functions__: These functions have two main properties. First, they always produce the same output for the same arguments irrespective of anything else. Secondly, they have no side-effects i.e. they do modify any argument or global variables or output something.\n",
    "\n",
    "* __Recursion__: There are no “for” or “while” loop in functional languages. Iteration in functional languages is implemented through recursion.\n",
    "\n",
    "* __Functions are First-Class and can be Higher-Order__: First-class functions are treated as first-class variable. The first-class variables can be passed to functions as a parameter, can be returned from functions or stored in data structures.\n",
    "\n",
    "* __Variables are Immutable__: In functional programming, we can’t modify a variable after it’s been initialized. We can create new variables – but we can’t modify existing variables."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1196e70",
   "metadata": {},
   "source": [
    "### Pure Functions\n",
    "As Discussed above, pure functions have two properties.\n",
    "\n",
    "* It always produces the same output for the same arguments. For example, 3+7 will always be 10 no matter what.\n",
    "It does not change or modifies the input variable.\n",
    "\n",
    "* The second property is also known as immutability. The only result of the Pure Function is the value it returns. They are deterministic. Programs done using functional programming are easy to debug because pure functions have no side effects or hidden I/O. Pure functions also make it easier to write parallel/concurrent applications. When the code is written in this style, a smart compiler can do many things – it can parallelize the instructions, wait to evaluate results when needing them, and memorize the results since the results never change as long as the input doesn’t change.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "90fdae63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original List: [1, 2, 3, 4]\n",
      "Modified List: [1, 4, 9, 16]\n"
     ]
    }
   ],
   "source": [
    "def pure_func(List):\n",
    "      \n",
    "    New_List = []\n",
    "      \n",
    "    for i in List:\n",
    "        New_List.append(i**2)\n",
    "          \n",
    "    return New_List\n",
    "\n",
    "Original_List = [1, 2, 3, 4]\n",
    "Modified_List = pure_func(Original_List)\n",
    "\n",
    "\n",
    "print(\"Original List:\", Original_List)\n",
    "print(\"Modified List:\", Modified_List)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71445ad5",
   "metadata": {},
   "source": [
    "## Recursion Function\n",
    "### What is recursion?\n",
    "* Recursion is the process of defining something in terms of itself.\n",
    "* A physical world example would be to place two parallel mirrors facing each other, any object in between them would be reflected recursively. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11454577",
   "metadata": {},
   "source": [
    "### Python Recursive Function\n",
    "* In Python, we know that a function can call other functions. It is even possible for the function to call itself. These types of construct are termed as recursive functions.\n",
    "\n",
    "* Using the recursive algorthm, certain problems can be solved quite easily.\n",
    "![打开方式](recursion.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23a02104",
   "metadata": {},
   "source": [
    "### Example: Fractorial of Integer\n",
    "Factorial of a number is the product of all the integers from 1 to that number.    \n",
    "For example, the factorial of 6 (denoted as 6!) is: 1x2x3x4x5x6 = 720\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2b0f92d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The factorial of 3 is 6\n"
     ]
    }
   ],
   "source": [
    "def factorial(x):\n",
    "    \"\"\"This is a recursive function\n",
    "    to find the factorial of an integer\"\"\"\n",
    "\n",
    "    if x == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return (x * factorial(x-1))\n",
    "\n",
    "\n",
    "num = 3\n",
    "print(\"The factorial of\", num, \"is\", factorial(num))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4aaf4f2",
   "metadata": {},
   "source": [
    "![打开方式](frac.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c14d02f6",
   "metadata": {},
   "source": [
    "* Our recursion ends when the number reduces to 1. This is called the __base condition.\n",
    "\n",
    "* Every recursive function must have a __base condition__ that stops the recursion or else the function calls itself infinitely.\n",
    "\n",
    "* The Python interpreter limits the depths of recursion to help avoid infinite recursions, resulting in stack overflows.\n",
    "\n",
    "* By default, the maximum depth of recursion is 1000. If the limit is crossed, it results in RecursionError. Let's look at one such condition."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d96d219f",
   "metadata": {},
   "source": [
    "### Example: Tower of Hanio\n",
    "![打开方式](TOH.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "d3ae0372",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move the disk S from S to A\n",
      "Move the disk S from S to D\n",
      "Move the disk A from A to D\n",
      "Move the disk S from S to A\n",
      "Move the disk D from D to S\n",
      "Move the disk D from D to A\n",
      "Move the disk S from S to A\n",
      "Move the disk S from S to D\n",
      "Move the disk A from A to D\n",
      "Move the disk A from A to S\n",
      "Move the disk D from D to S\n",
      "Move the disk A from A to D\n",
      "Move the disk S from S to A\n",
      "Move the disk S from S to D\n",
      "Move the disk A from A to D\n"
     ]
    }
   ],
   "source": [
    "# Assuming n-th disk is\n",
    "# bottom disk (count down)\n",
    "def tower(n, sourcePole, destinationPole, auxiliaryPole):\n",
    " \n",
    "    # Base case (termination condition)\n",
    "    if(0 == n):\n",
    "        return\n",
    "     \n",
    "    # Move first n-1 disks\n",
    "    # from source pole\n",
    "    # to auxiliary pole\n",
    "    # using destination as\n",
    "    # temporary pole\n",
    "    tower(n-1, sourcePole, auxiliaryPole, destinationPole)\n",
    "\n",
    "    # Move the n-1 disks from\n",
    "    # auxiliary (now source)\n",
    "    # pole to destination pole\n",
    "    # using source pole as\n",
    "    # temporary (auxiliary) pole\n",
    "    tower(n-1, auxiliaryPole, destinationPole,sourcePole)\n",
    " \n",
    " \n",
    "# Driver code\n",
    "tower(4, 'S', 'D', 'A')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df8e155c",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "* In a party of N people, each person will shake her/his hand with each other person only once.\n",
    "* In total how many hand-shakes would happen?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fb52c74",
   "metadata": {},
   "source": [
    "__Solution__:\n",
    "* It can be solved in different ways; graphs, recursions, etc. Let us see how recursively it can be solved.\n",
    "\n",
    "* There are N persons. Each person shakes hands with each other only once. Considering N-th person, (s)he has to shake a hand with (N-1) the person. Now the problem is reduced to small instances of (N-1) persons. Assuming TN as a total shake-hands, it can be formulated recursively.\n",
    "\n",
    "* TN = (N-1) + TN-1 [T1 = 0, i.e. the last person has already shook-hand with every one]\n",
    "\n",
    "* Solving it recursively yields an arithmetic series, which can be evaluated into N(N-1)/2.\n",
    "\n",
    "* Exercise: In a party of N couples, only one gender (either male or female) can shake hands with everyone. How many shake-hands would happen?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ca966aa",
   "metadata": {},
   "source": [
    "### Advantages of Recursion\n",
    "* Recursive functions make the code look clean and elegant.\n",
    "* A complex task can be broken down into simpler sub-problems using recursion.\n",
    "* Sequence generation is easier with recursion than using some nested iteration.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f483bbf",
   "metadata": {},
   "source": [
    "### Disadvantages of Recursion\n",
    "* Sometimes the logic behind recursion is hard to follow through.\n",
    "* Recursive calls are expensive (inefficient) as they take up a lot of memory and time.\n",
    "* Recursive functions are hard to debug."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bb89493",
   "metadata": {},
   "source": [
    "### Functional Style\n",
    "\n",
    "Functional programming typically uses lists, arrays, and other iterables to represent the data along with a set of functions that operate on that data and transform it. When it comes to processing data with a __functional style__, there are at least three commonly used techniques:\n",
    "\n",
    "* __Mapping__ consists of applying a transformation function to an iterable to produce a new iterable. Items in the new iterable are produced by calling the transformation function on each item in the original iterable.\n",
    "\n",
    "* __Filtering__ consists of applying a predicate or Boolean-valued function to an iterable to generate a new iterable. Items in the new iterable are produced by filtering out any items in the original iterable that make the predicate function return false.\n",
    "\n",
    "* __Reducing__ consists of applying a reduction function to an iterable to produce a single cumulative value.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10f2e732",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7ea81f4d",
   "metadata": {},
   "source": [
    "### Mapping\n",
    "* Sometimes you might face situations in which you need to perform the same operation on all the items of an input iterable to build a new iterable. The quickest and most common approach to this problem is to use a Python for loop. However, you can also tackle this problem without an explicit loop by using __map().   \n",
    "* __map()__ loops over the items of an input iterable (or iterables) and returns an iterator that results from applying a transformation function to every item in the original input iterable.\n",
    "\n",
    "* According to the documentation, __map()__ takes a function object and an iterable (or multiple iterables) as arguments and returns an iterator that yields transformed items on demand. The function’s signature is defined as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "261f634f",
   "metadata": {},
   "source": [
    "* map(function, iterable[, iterable1, iterable2,..., iterableN]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e257d93",
   "metadata": {},
   "source": [
    "* __map()__ applies function to each item in iterable in a loop and returns a new iterator that yields transformed items on demand. function can be any Python function that takes a number of arguments equal to the number of iterables you pass to __map().\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b1e5de8",
   "metadata": {},
   "source": [
    "* This first argument to __map()__ is a transformation function. In other words, it’s the function that transforms each original item into a new (transformed) item. Even though the Python documentation calls this argument function, it can be any Python callable. This includes __built-in functions, classes, methods, lambda functions, and user-defined functions__.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95308913",
   "metadata": {},
   "source": [
    "* The operation that __map()__ performs is commonly known as a __mapping__ because it maps every item in an input iterable to a new item in a resulting iterable. To do that, __map()__ applies a transformation function to all the items in the input iterable.\n",
    "\n",
    "* To better understand __map()__, suppose you need to take a list of numeric values and transform it into a list containing the square value of every number in the original list. In this case, you can use a for loop and code something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "7f9cc425",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = [1, 2, 3, 4, 5]\n",
    "squared = []\n",
    "\n",
    "for num in numbers:\n",
    "    squared.append(num ** 2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51a7cf87",
   "metadata": {},
   "source": [
    "* When you run this loop on numbers, you get a list of square values. The for loop iterates over numbers and applies a power operation on each value. Finally, it stores the resulting values in squared.\n",
    "\n",
    "* You can achieve the same result without using an explicit loop by using __map()__. Take a look at the following reimplementation of the above example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "642a7cbb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def square(number):\n",
    "    return number ** 2\n",
    "\n",
    "numbers = [1, 2, 3, 4, 5]\n",
    "\n",
    "squared = map(square, numbers)\n",
    "list(squared)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1da683e2",
   "metadata": {},
   "source": [
    "* Since __map()__ is written in C and is highly optimized, its internal implied loop can be more efficient than a regular Python for loop. This is one advantage of using __map()__.\n",
    "\n",
    "* A second advantage of using __map()__ is related to memory consumption. With a for loop, you need to store the whole list in your system’s memory. With map(), you get items on demand, and only one item is in your system’s memory at a given time."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f94f428",
   "metadata": {},
   "source": [
    "* For another example, say you need to convert all the items in a list from a string to an integer number. To do that, you can use __map()__ along with __int()__ as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "80fdf69c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<map at 0x7fd69baa01c0>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str_nums = [\"4\", \"8\", \"6\", \"5\", \"3\", \"2\", \"8\", \"9\", \"2\", \"5\"]\n",
    "int_nums = map(int, str_nums)\n",
    "int_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "da81b95a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 8, 6, 5, 3, 2, 8, 9, 2, 5]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(int_nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70b20cb0",
   "metadata": {},
   "source": [
    "### Using map() With Different Kinds of Functions\n",
    "* You can use any kind of Python callable with __map()__. The only condition would be that the callable takes an argument and returns a concrete and useful value. For example, you can use classes, instances that implement a special method called __call__(), instance methods, class methods, static methods, and functions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "920a9c57",
   "metadata": {},
   "source": [
    "There are some built-in functions that you can use with map(). Consider the following examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "dcf443d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 0, 1, 2]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = [-2, -1, 0, 1, 2]\n",
    "abs_values = list(map(abs, numbers))\n",
    "abs_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "86ba8f2a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0, 2.0, 3.0, 4.0, 5.0]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(float, numbers))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "db496dfe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 2, 4, 6]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = [\"Welcome\", \"to\", \"Real\", \"Python\"]\n",
    "list(map(len, words))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c50154a4",
   "metadata": {},
   "source": [
    "* You can use any __built-in function with map()__, provided that the function takes an argument and returns a value.\n",
    "\n",
    "* A common pattern that you’ll see when it comes to using __map()__ is to use a __lambda function__ as the first argument. lambda functions are handy when you need to pass an expression-based function to __map()__. For example, you can reimplement the example of square values using a lambda function as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "d8c01c8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = [1, 2, 3, 4, 5]\n",
    "squared = map(lambda num: num ** 2, numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "11d3ff22",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(squared)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae2bb284",
   "metadata": {},
   "source": [
    "### Processing Multiple Input Iterables With map()\n",
    "* If you supply multiple iterables to map(), then the transformation function must take as many arguments as iterables you pass in. Each iteration of __map()__ will pass one value from each iterable as an argument to function. The iteration stops at the end of the shortest iterable.\n",
    "\n",
    "* Consider the following example that uses pow():"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "2ffa0df4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 32, 729]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "first_it = [1, 2, 3]\n",
    "second_it = [4, 5, 6, 7]\n",
    "list(map(pow, first_it, second_it))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05f67736",
   "metadata": {},
   "source": [
    "__pow()__ takes two arguments, x and y, and returns x to the power of y. In the first iteration, x will be 1, y will be 4, and the result will be 1. In the second iteration, x will be 2, y will be 5, and the result will be 32, and so on. The final iterable is only as long as the shortest iterable, which is first_it in this case."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a81e112f",
   "metadata": {},
   "source": [
    "* This technique allows you to merge two or more iterables of numeric values using different kinds of math operations. Here are some examples that use lambda functions to perform different math operations on several input iterables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "db7b64f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x, y: x - y, [2, 4, 6], [1, 3, 5]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "9f22a877",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 15]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x, y, z: x + y + z, [2, 4], [1, 3], [7, 8]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d146b038",
   "metadata": {},
   "source": [
    "### Filtering\n",
    "\n",
    "Python’s __filter()__ is a built-in function that allows you to process an iterable and extract those items that satisfy a given condition. This process is commonly known as a filtering operation. With filter(), you can apply a filtering function to an iterable and produce a new iterable with the items that satisfy the condition at hand. In Python, filter() is one of the tools you can use for functional programming."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e541ad5c",
   "metadata": {},
   "source": [
    "* Say you need to process a list of numbers and return a new list containing only those numbers greater than 0. A quick way to approach this problem is to use a for loop like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "4a80ec7a",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = [-2, -1, 0, 1, 2]\n",
    "\n",
    "def extract_positive(numbers):\n",
    "    positive_numbers = []\n",
    "    for number in numbers:\n",
    "        if number > 0:  # Filtering condition\n",
    "            positive_numbers.append(number)\n",
    "    return positive_numbers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "687a3a46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extract_positive(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fb893b4",
   "metadata": {},
   "source": [
    "* The loop in extract_positive() iterates through numbers and stores every number greater than 0 in positive_numbers. The conditional statement filters out the negative numbers and 0. This kind of functionality is known as a __filtering.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71242bcb",
   "metadata": {},
   "source": [
    "* Filtering operations consist of testing each value in an iterable with a condition function and retaining only those values for which the function produces a true result. \n",
    "\n",
    "* Filtering operations are fairly common in programming, so most programming languages provide tools to approach them. In the next section, you’ll learn about Python’s way to filter iterables."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5107821",
   "metadata": {},
   "source": [
    "Python provides a convenient built-in function, __filter()__, that abstracts out the logic behind filtering operations. Here’s its signature:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "122a60c9",
   "metadata": {},
   "source": [
    "* filter(function, iterable)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05ae8d9b",
   "metadata": {},
   "source": [
    "* The first argument, function, must be a single-argument function. \n",
    "* Typically, you provide a condition (Boolean-valued) function to this argument. In other words, you provide a function that returns either True or False according to a specific condition."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d551ba0",
   "metadata": {},
   "source": [
    "__Note: The first argument to filter() is a function object, which means that you need to pass a function without calling it with a pair of parentheses.__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d59b7cf2",
   "metadata": {},
   "source": [
    "* The second argument, iterable, can hold any Python iterable, such as a list, tuple, or set. It can also hold generator and iterator objects. An important point regarding filter() is that it accepts only one iterable.\n",
    "\n",
    "* To perform the filtering process, __filter()__ applies function to every item of iterable in a loop. The result is an iterator that yields the values of iterable for which function returns a true value. __The process doesn’t modify the original input iterable.__\n",
    "\n",
    "* Since filter() is written in C and is highly optimized, its internal implicit loop can be more efficient than a regular for loop regarding execution time. This efficiency is arguably the most important advantage of using the function in Python.\n",
    "\n",
    "* A second advantage of using __filter()__ over a loop is that it returns a filter object, which is an iterator that yields values on demand, promoting a lazy evaluation strategy. Returning an iterator makes filter() more memory efficient than an equivalent for loop."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31572ae9",
   "metadata": {},
   "source": [
    "__Note: In Python 2.x, filter() returns list objects. This behavior changed in Python 3.x. Now the function returns a filter object, which is an iterator that yields items on demand. Python iterators are well known to be memory efficient.__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3faf4f17",
   "metadata": {},
   "source": [
    "In the above example about positive numbers, you can use __filter()__ along with a convenient predicate function to extract the desired numbers. To code the predicate, you can use either a lambda or a user-defined function:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "0ea98d4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<filter at 0x7fd69bd29220>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# use a lambda function\n",
    "numbers = [-2, -1, 0, 1, 2]\n",
    "positive_numbers = filter(lambda n: n > 0, numbers)\n",
    "positive_numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "a97e9ed2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(positive_numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "642aea7d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# use a user-defined function\n",
    "def is_positive(n):\n",
    "    return n>0\n",
    "\n",
    "\n",
    "list(filter(is_positive, numbers))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "cdab8c55",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def identity(x):\n",
    "    return x\n",
    "\n",
    "identity(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "44a97452",
   "metadata": {},
   "outputs": [],
   "source": [
    "objects = [0, 1, [], 4, 5, \"\", None, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "ecfbe6e2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 5, 8]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(identity, objects))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1eb8bd40",
   "metadata": {},
   "source": [
    "* In this example, the filtering function, __identity()__, doesn’t return True or False explicitly but the same argument it takes. Since 0, [], \"\", and None are falsy, filter() uses their truth value to filter them out. The final list contains only those values that are truthy in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17e2e62b",
   "metadata": {},
   "source": [
    "Finally, if you pass None to function, then filter() uses the identity function and yields all the elements of iterable that evaluate to True:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "9e53ea73",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 5, 8]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objects = [0, 1, [], 4, 5, \"\", None, 8]\n",
    "list(filter(None, objects))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5e925d2",
   "metadata": {},
   "source": [
    "### Extracting Even Numbers\n",
    "\n",
    "As a first example, say you need to process a list of integer numbers and build a new list containing the even numbers. Your first approach to this problem might be to use a for loop like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "affb3af7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 6, 50]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = [1, 3, 10, 45, 6, 50]\n",
    "\n",
    "def extract_even(numbers):\n",
    "    even_numbers = []\n",
    "    for number in numbers:\n",
    "        if number%2 == 0:\n",
    "            even_numbers.append(number)\n",
    "    return even_numbers\n",
    "        \n",
    "extract_even(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71b448ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "you can perform the same computation without using an explicit loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "d801c6e3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 6, 50]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = [1, 3, 10, 45, 6, 50]\n",
    "def is_even(number):\n",
    "    return number%2 == 0 #condition\n",
    "\n",
    "list(filter(is_even, numbers))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9c70d17",
   "metadata": {},
   "source": [
    "* Here, __is_even()__ takes an integer and returns True if it’s even and False otherwise. The call to __filter()__ does the hard work and filters out the odd numbers. As a result, you get a list of the even numbers. \n",
    "\n",
    "* This code is shorter and more efficient than its equivalent for loop.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d694d8f",
   "metadata": {},
   "source": [
    "### Finding Prime Numbers\n",
    "\n",
    "Another interesting example might be to extract all the prime numbers in a given interval. To do that, you can start by coding a predicate function that takes an integer as an argument and returns True if the number is prime and False otherwise. Here’s how you can do that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "caaed324",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "def is_prime(n):\n",
    "    if n <= 1:\n",
    "        return False\n",
    "    for i in range(2, int(math.sqrt(n)) + 1):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        return True\n",
    "    \n",
    "is_prime(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7927fa62",
   "metadata": {},
   "source": [
    "* The filtering logic is now in __is_prime()__. The function iterates through the integers between 2 and the square root of n. Inside the loop, the conditional statement checks if the current number is divisible by any other in the interval. If so, then the function returns False because the number isn’t prime. Otherwise, it returns True to signal that the input number is prime.\n",
    "\n",
    "* With is_prime() in place and tested, you can use filter() to extract prime numbers from an interval like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "08d30556",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5,\n",
       " 7,\n",
       " 9,\n",
       " 11,\n",
       " 13,\n",
       " 15,\n",
       " 17,\n",
       " 19,\n",
       " 21,\n",
       " 23,\n",
       " 25,\n",
       " 27,\n",
       " 29,\n",
       " 31,\n",
       " 33,\n",
       " 35,\n",
       " 37,\n",
       " 39,\n",
       " 41,\n",
       " 43,\n",
       " 45,\n",
       " 47,\n",
       " 49]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(is_prime, range(1,51)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25cbbe28",
   "metadata": {},
   "source": [
    "### Removing Outliers in a Sample\n",
    "\n",
    "* When you’re trying to describe and summarize a sample of data, you probably start by finding its __mean, or average__. The mean is a quite popular central tendency measurement and is often the first approach to analyzing a dataset. __It gives you a quick idea of the center, or location, of the data__.\n",
    "\n",
    "* In some cases, the mean isn’t a good enough central tendency measure for a given sample. __Outliers__ are one of the elements that affect how accurate the mean is. Outliers are data points that differ significantly from other observations in a sample or population. Other than that, there is no unique mathematical definition for them in statistics.\n",
    "\n",
    "* However, in normally distributed samples, __outliers are often defined as data points that lie more than two standard deviations from the sample mean__.\n",
    "\n",
    "* Now suppose you have a normally distributed sample with some outliers that are affecting the mean accuracy. You’ve studied the outliers, and you know they’re incorrect data points. Here’s how you can use a couple of functions from the statistics module along with filter() to clean up your data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "dcc0039d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.692307692307692"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import statistics as st\n",
    "sample = [10, 8, 10, 8, 2, 7, 9, 3, 34, 9, 5, 9, 25]\n",
    "# the mean before moving the outliers\n",
    "mean = st.mean(sample)\n",
    "mean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "a70688c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 8, 10, 8, 2, 7, 9, 3, 9, 5, 9, 25]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stdev = st.stdev(sample)\n",
    "low = mean - 2 * stdev\n",
    "high = mean + 2*stdev\n",
    "\n",
    "clean_sample = list(filter(lambda x: low<= x <= high, sample))\n",
    "clean_sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "ef161b6b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.75"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.mean(clean_sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbdf15da",
   "metadata": {},
   "source": [
    "### reduce()\n",
    "\n",
    "* Python’s __reduce()__ is a function that implements a mathematical technique called folding or reduction.\n",
    "* You’re doing a fold or reduction when you reduce a list of items to a single cumulative value. Python’s reduce() operates on any iterable—not just lists—and performs the following steps:\n",
    "    * __Apply__ a function (or callable) to the first two items in an iterable and generate a partial result.\n",
    "    * __Use__ that partial result, together with the third item in the iterable, to generate another partial result.\n",
    "    * __Repeat__ the process until the iterable is exhausted and then return a single cumulative value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2ce7992",
   "metadata": {},
   "source": [
    "In general, Python’s reduce() is handy for processing iterables without writing explicit for loops. Since reduce() is written in C, its internal loop can be faster than an explicit Python for loop.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e89522c",
   "metadata": {},
   "source": [
    "* Python’s __reduce()__ was originally a built-in function (and still is in Python 2.x), but it was moved to __functools.__ __reduce()__ in Python 3.0. This decision was based on some possible performance and readability issues.\n",
    "\n",
    "* Another reason for moving __reduce()__ to __functools__ was the introduction of built-in functions like sum(), any(), all(), max(), min(), and len(), which provide more efficient, readable, and Pythonic ways of tackling common use cases for reduce(). You’ll learn how to use them in place of reduce() later in the tutorial.\n",
    "\n",
    "* In Python 3.x, if you need to use reduce(), then you first have to import the function into your current scope using an import statement in one of the following ways:\n",
    "\n",
    "    * __import functools__ and then use fully-qualified names like __functools.reduce().__\n",
    "    * __from functools import reduce__ and then call __reduce()__ directly.\n",
    "    \n",
    "According to the documentation for reduce(), the function has the following signature:\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "980597ed",
   "metadata": {},
   "source": [
    "* functools.reduce(function, iterable[, initializer])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01baf52e",
   "metadata": {},
   "source": [
    "The Python documentation also states that reduce() is roughly equivalent to the following Python function:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "d514ea70",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def reduce(function, iterable, initializer=None):\n",
    "    it = iter(iterable)\n",
    "    if initializer is None:\n",
    "        value = next(it)\n",
    "    else:\n",
    "        value = initializer\n",
    "    for element in it:\n",
    "        value = function(value, element)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2268dfb",
   "metadata": {},
   "source": [
    "### The Required Arguments: function and iterable\n",
    "\n",
    "* The first argument to Python’s __reduce()__ is a two-argument function conveniently called function. This function will be applied to the items in an iterable to cumulatively compute a final value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13af25db",
   "metadata": {},
   "source": [
    "* The second required argument, iterable, will accept any Python iterable, as its name suggests. This includes lists, tuples, range objects, generators, iterators, sets, dictionary keys and values, and any other Python objects that you can iterate over."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "403f60ec",
   "metadata": {},
   "source": [
    "* To understand how reduce() works, you’re going to write a function that computes the sum of two numbers and prints the equivalent math operation to the screen. Here’s the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "6ac86bdd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_add(a, b):\n",
    "    result = a + b\n",
    "    print(f\"{a} + {b} = {result}\")\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "c256e4e5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 + 5 = 10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_add(5,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1cd16f1",
   "metadata": {},
   "source": [
    "* __my_add()__ is a two-argument function, so you can pass it to Python’s reduce() along with an iterable to compute the cumulated sum of the items in the iterable. Check out the following code that uses a list of numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "d77c5242",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 + 1 = 1\n",
      "1 + 2 = 3\n",
      "3 + 3 = 6\n",
      "6 + 4 = 10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "numbers = [0, 1, 2, 3, 4]\n",
    "reduce(my_add, numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26914b94",
   "metadata": {},
   "source": [
    "When you call reduce(), passing my_add() and numbers as arguments, you get an output that shows all the operations that reduce() performs to come up with a final result of 10.    \n",
    "* In this case, the operations are equivalent to ((((0 + 1) + 2) + 3) + 4) = 10."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e5ea285",
   "metadata": {},
   "source": [
    "### The Optional Argument: initializer\n",
    "\n",
    "The third argument to Python’s __reduce()__, called initializer, is optional. If you supply a value to initializer, then reduce() will feed it to the first call of function as its first argument."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b36ab188",
   "metadata": {},
   "source": [
    "* This means that the first call to function will use the value of initializer and the first item of iterable to perform its first partial computation. After this, reduce() continues working with the subsequent items of iterable."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b91bdbfe",
   "metadata": {},
   "source": [
    "Here’s an example in which you use my_add() with initializer set to 100:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "2789aaee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 + 0 = 100\n",
      "100 + 1 = 101\n",
      "101 + 2 = 103\n",
      "103 + 3 = 106\n",
      "106 + 4 = 110\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "110"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "numbers = [0, 1, 2, 3, 4]\n",
    "reduce(my_add, numbers, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c995d1f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
